#ifndef SPARSEMATRIX_H_
#define SPARSEMATRIX_H_

#include "SparseMatrix Point.h"
#include<iostream>
#include<vector>
#include<iomanip>
#include<cstdlib>
using namespace std;

template <typename Type>
class SparseMatrix {
	template <typename Type>
	friend ostream &operator<<(ostream &output, SparseMatrix<Type> &Matrix);
	template <typename Type>
	friend istream &operator>>(istream &input, SparseMatrix<Type> &Matrix);
public:


	SparseMatrix(int row = 10, int col = 10, int total = 0);
	SparseMatrix(Point<Type> *ptr,int row = 10, int col = 10, int total = 0);
	SparseMatrix(SparseMatrix<Type> &Matrix);
	~SparseMatrix();

	SparseMatrix<Type> &operator+(SparseMatrix<Type> &Matrix);
	SparseMatrix<Type> &operator-(SparseMatrix<Type> &Matrix);
	SparseMatrix<Type> &operator*(SparseMatrix<Type> &Matrix);
	SparseMatrix<Type> &Transpose();							

	int getRow();
	int getCol();
	int getTol();
	Point<Type> *getBase();

	Status setRow(int row);
	Status setCol(int col);
	Status setTol(int total);

private:

	Point<Type> *m_pBase;
	int m_iRowNum;
	int m_iColNum;
	int m_iTolNum;

};


template <typename Type>
istream &operator>>(istream &input, SparseMatrix<Type> &Matrix) {
	cout << "please input x,y and data.(row first)" << endl;
	cout << "Total: " << Matrix.getTol() << endl;
	int x;
	int y;
	Type data;
	Point<Type> *ptr = Matrix.getBase();
	for (; ptr < Matrix.getBase() + Matrix.getTol(); ++ptr) {
		input >> x >> y >> data;
		ptr->setX(x);
		ptr->setY(y);
		ptr->setData(data);
	}
	return input;
}

template <typename Type>
ostream &operator<<(ostream &output, SparseMatrix<Type> &Matrix) {
	//row first
	output << endl;
	if (Matrix.getTol() == 0) {
		output << "No Element!" << endl;
		return output;
	}
	int tol = Matrix.getTol();
	int row = Matrix.getRow();
	int col = Matrix.getCol();
	Point<Type> *pointer = Matrix.getBase();
	for (int i = 1; i <= row; ++i) {
		for (int j = 1; j <= col; ++j) {
			if (pointer->getX() == i && pointer->getY() == j) {		
				output << setw(3) << pointer->getData();
				++pointer;
			}
			else {
				output << "  0";
			}
			output << ' ';
		}
		output << endl;
	}
	output << endl;
	return output;
}

template<typename Type>
SparseMatrix<Type>::SparseMatrix(int row, int col, int total)
					:m_iRowNum(row), m_iColNum(col), m_iTolNum(total), m_pBase(NULL){
	m_pBase = new Point<Type>[m_iTolNum];
	if (m_pBase == NULL) {
		perror("Failed to allocate memory! EXIT NOW!");
		exit(EXIT_FAILURE);
	}
}

template<typename Type>
SparseMatrix<Type>::SparseMatrix(Point<Type>* ptr, int row, int col, int total)
					:m_iRowNum(row), m_iColNum(col), m_iTolNum(total), m_pBase(NULL){
	m_pBase = new Point<Type>[m_iTolNum];
	if (m_pBase == NULL) {
		perror("Failed to allocate memory! EXIT NOW!");
		exit(EXIT_FAILURE);
	}
	Point<Type> *ptr2 = ptr;
	Point<Type> *ptr1 = m_pBase;
	for (int i = 0; i < m_iTolNum; ++i) {
		*ptr1++ = *ptr2++;
	}
}

template<typename Type>
SparseMatrix<Type>::SparseMatrix(SparseMatrix<Type>& Matrix){
	m_iRowNum = Matrix.getRow();
	m_iColNum = Matrix.getCol();
	m_iTolNum = Matrix.getTol();
	if (m_pBase != NULL) {
		delete[] m_pBase;
	}
	m_pBase = new Point<Type>[m_iTolNum];
	if (m_pBase == NULL) {
		perror("Failed to allocate memory! EXIT NOW!");
		exit(EXIT_FAILURE);
	}
	Point<Type> *ptr2 = Matrix.getBase();
	Point<Type> *ptr1 = this->getBase();
	for (int i = 0; i < m_iTolNum; ++i) {
		*ptr1++ = *ptr2++;
	}
}

template<typename Type>
SparseMatrix<Type>::~SparseMatrix(){
	delete[] m_pBase;
	m_pBase = NULL;
}

template<typename Type>
SparseMatrix<Type>& SparseMatrix<Type>::operator+(SparseMatrix<Type>& Matrix){
	
	if ((this->getRow() == Matrix.getRow()) && 
		(this->getCol() == Matrix.getCol())) {

		//ptr Used to temporarily store sum of the two matrix 
		Point<Type> *ptr = new Point<Type>[this->getTol() + Matrix.getTol()];	
		if (ptr == NULL) {
			perror("Failed to allocate memory!\n");
			exit(EXIT_FAILURE);
		}

		Point<Type> *ptrBase = ptr;						//ptrBase to keep the beginning of sum matrix;
		Point<Type> *ptr1 = this->getBase();			//ptr1 point to the first matrix;
		Point<Type> *ptr1End = ptr1 + this->getTol();	//ptr1End point to the end of the first matrix;
		Point<Type> *ptr2 = Matrix.getBase();			//as ptr1
		Point<Type> *ptr2End = ptr2 + Matrix.getTol();	//as ptr1End

		//add
		while (ptr1 != ptr1End && ptr2 != ptr2End) {

			int x1 = ptr1->getX();
			int y1 = ptr1->getY();
			int x2 = ptr2->getX();
			int y2 = ptr2->getY();
			
			//*ptr1 in the top left of *ptr2
			if (x1 < x2 || (x1 == x2 && y1 < y2)) {
				*ptr = *ptr1;
				++ptr;
				++ptr1;
			}
			//*ptr1 in the down right of *ptr2
			else if (x1 > x2 || (x1 == x2 && y1 > y2)) {
				*ptr = *ptr2;
				++ptr;
				++ptr2;
			}
			//*ptr1 and *ptr2 are at the same position;
			else{
				Type sum;
				if (sum = ptr1->getData() + ptr2->getData()) {
					ptr->setX(x1);
					ptr->setY(y1);
					ptr->setData(sum);
					++ptr;
				}
				++ptr1;
				++ptr2;
			}
		}
		while (ptr1 != ptr1End) {
			*ptr++ = *ptr1++;
		}
		while (ptr2 != ptr2End) {
			*ptr++ = *ptr2++;
		}

		SparseMatrix<Type> *sumMatrix = new SparseMatrix<Type>(ptrBase, this->getRow(), this->getCol(), ptr - ptrBase);
		
		delete[] ptrBase;
		ptrBase = NULL;
		
		return *sumMatrix;
	}
	else {
		perror("Illegal type of matrixs!\n");
		exit(EXIT_FAILURE);
	}
}

template<typename Type>
SparseMatrix<Type>& SparseMatrix<Type>::operator-(SparseMatrix<Type>& Matrix){
	if ((this->getRow() == Matrix.getRow()) &&
		(this->getCol() == Matrix.getCol())) {

		//ptr Used to temporarily store result of the operation 
		Point<Type> *ptr = new Point<Type>[this->getTol() + Matrix.getTol()];
		if (ptr == NULL) {
			perror("Failed to allocate memory!\n");
			exit(EXIT_FAILURE);
		}
		Point<Type> *ptrBase = ptr;						//ptrBase to keep the beginning of sum matrix;
		Point<Type> *ptr1 = this->getBase();			//ptr1 point to the first matrix;
		Point<Type> *ptr1End = ptr1 + this->getTol();	//ptr1End point to the end of the first matrix;
		Point<Type> *ptr2 = Matrix.getBase();			//as ptr1
		Point<Type> *ptr2End = ptr2 + Matrix.getTol();	//as ptr1End

														//calculate
		while (ptr1 != ptr1End && ptr2 != ptr2End) {

			int x1 = ptr1->getX();
			int y1 = ptr1->getY();
			int x2 = ptr2->getX();
			int y2 = ptr2->getY();

			//*ptr1 in the top left of *ptr2
			if (x1 < x2 || (x1 == x2 && y1 < y2)) {
				*ptr = *ptr1;
				++ptr;
				++ptr1;
			}
			//*ptr1 in the down right of *ptr2
			else if (x1 > x2 || (x1 == x2 && y1 > y2)) {
				ptr->setX(x2);
				ptr->setY(y2);
				ptr->setData(-ptr2->getData());
				++ptr;
				++ptr2;
			}
			//*ptr1 and *ptr2 are at the same position;
			else {
				Type sum;
				if (sum = ptr1->getData() - ptr2->getData()) {
					ptr->setX(x1);
					ptr->setY(y1);
					ptr->setData(sum);
					++ptr;
				}
				++ptr1;
				++ptr2;
			}
		}
		while (ptr1 != ptr1End) {
			*ptr++ = *ptr1++;
		}
		while (ptr2 != ptr2End) {
			ptr->setX(ptr2->getX());
			ptr->setY(ptr2->getY());
			ptr->setData(-ptr2->getData());
			++ptr;
			++ptr2;
		}

		int total = ptr - ptrBase;
		SparseMatrix<Type> *newOne = new SparseMatrix<Type>(ptrBase, this->getRow(), this->getCol(), total);
		
		delete[] ptrBase;
		ptrBase = NULL;
		
		return *newOne;
	}
	else {
		perror("Illegal type of matrixs!\n");
		exit(EXIT_FAILURE);
	}
}

template<typename Type>
SparseMatrix<Type>& SparseMatrix<Type>::operator*(SparseMatrix<Type>& Matrix){

	if (this->getCol() == Matrix.getRow()) {

		//ptr Used to temporarily store result of the operation
		Point<Type> *ptr = new Point<Type>[this->getRow() * Matrix.getCol()];
		if (ptr == NULL) {
			perror("Failed to allocate memory!\n");
			exit(EXIT_FAILURE);
		}

		Point<Type> *ptrBase = ptr;						//ptrBase to keep the beginning of sum matrix;
		Point<Type> *ptrEnd = ptr;
		Point<Type> *thisptrEnd = this->getBase() + this->getTol();	//ptr1End point to the end of the first matrix;
		Point<Type> *thisptr;

		vector<Type> mid(Matrix.getCol());						//to store mid value
		vector<int> num(Matrix.getRow());
		vector<int> pos(Matrix.getRow());
		pos[0] = 0;

		for (int i = 0; i < (int)num.size(); ++i) 
			num[i] = 0;
		
		//0--Row-1 ==1--Row 
		for (ptr = Matrix.getBase(); ptr < Matrix.getBase() + Matrix.getTol(); ++ptr)		
			++num[ptr->getX() - 1];

		//keep the pos of the beginning of every line 
		//0--Row-1 ==1--Row
		for (int i = 1; i < (int)pos.size(); ++i)					
			pos[i] = pos[i - 1] + num[i - 1];
		
		//calculate
		int x = -1;	//mark the current line
		for (thisptr = this->getBase(), ptrEnd = ptrBase; thisptr < thisptrEnd; ++thisptr) {
			
			//if there is a new line, ini mid[] and update x
			if (thisptr->getX() != x) {	
				for (int i = 0; i < Matrix.getCol(); ++i)
					mid[i] = 0;
				x = thisptr->getX();
			}

			//calculate *
			Type data = thisptr->getData();

			int row = thisptr->getY();
			ptr = Matrix.getBase() + pos[row - 1];

			for (int i = 0; i < num[row - 1]; ++i, ++ptr) {
				if(ptr->getX() == row)
					mid[ptr->getY() - 1] += data * ptr->getData();
			}

			//when reach a new line add data except 0
			Point<Type> *temp = thisptr + 1;
			if(temp == thisptrEnd || temp->getX() != thisptr->getX())
				for (int i = 0; i < Matrix.getCol(); ++i) {
					if (mid[i]) {
						ptrEnd->setX(x);
						ptrEnd->setY(i + 1);
						ptrEnd->setData(mid[i]);
						++ptrEnd;
					}
				}
		}

		SparseMatrix<Type> *newOne = new SparseMatrix<Type>(ptrBase, this->getRow(), Matrix.getCol(), ptrEnd - ptrBase);

		delete[] ptrBase;
		ptrBase = NULL;

		return *newOne;
	}
	else {
		perror("Illegal type of matrixs!\n");
		exit(EXIT_FAILURE);
	}

}

template<typename Type>
SparseMatrix<Type>& SparseMatrix<Type>::Transpose(){

	Point<Type> *ptr = new Point<Type>[this->getTol()];
	if (ptr == NULL) {
		perror("Failed to allocate memory!\n");
		exit(EXIT_FAILURE);
	}

	vector<int> num(this->getCol());
	vector<int> pos(this->getCol());
	pos[0] = 0;
	for (int i = 0; i < (int)num.size(); ++i) {
		num[i] = 0;
	}
	Point<Type> *ptrBase = ptr;									//ptrBase to keep the beginning of sum matrix;
	Point<Type> *thisptrEnd = this->getBase() + this->getTol();	//ptr1End point to the end of the first matrix;
	
	for (ptr = this->getBase(); ptr < thisptrEnd; ++ptr) {
		++num[ptr->getY() - 1];
	}
	for (int i = 1; i < (int)pos.size(); ++i) {
		pos[i] = pos[i - 1] + num[i - 1];
	}
	for (Point<Type> *curPtr = this->getBase(); curPtr < thisptrEnd; ++curPtr) {
		ptr = ptrBase + pos[curPtr->getY() - 1];
		ptr->setX(curPtr->getY());
		ptr->setY(curPtr->getX());
		ptr->setData(curPtr->getData());
		++pos[curPtr->getY() - 1];
	}

	SparseMatrix<Type> *resultMatrix = new SparseMatrix<Type>(ptrBase, this->getCol(), this->getRow(), this->getTol());

	delete[] ptrBase;
	ptrBase = NULL;

	return *resultMatrix;
}

template<typename Type>
int SparseMatrix<Type>::getRow(){
	return m_iRowNum;
}

template<typename Type>
int SparseMatrix<Type>::getCol(){
	return m_iColNum;
}

template<typename Type>
int SparseMatrix<Type>::getTol(){
	return m_iTolNum;
}

template<typename Type>
Point<Type> *SparseMatrix<Type>::getBase(){
	return m_pBase;
}

template<typename Type>
Status SparseMatrix<Type>::setRow(int row){
	m_iRowNum = row;
	return OK;
}

template<typename Type>
Status SparseMatrix<Type>::setCol(int col){
	m_iColNum = col;
	return OK;
}

template<typename Type>
Status SparseMatrix<Type>::setTol(int total){
	m_iTolNum = total;
	return OK;
}


#endif